Inteligencia Artificial

1 Contenido de la clase

Repaso: búsqueda en espacios de estados y problemas de restricciones [04:48-07:53]

En los problemas de camino la pregunta es "¿cómo llego del estado inicial al estado final?" y los caminos y costos tienen unicidad. En un CSP la meta es un estado (una asignación completa que cumple las restricciones), no un camino: en Sudoku "no hay camino", solo importa llenar las 81 casillas con las reglas. Un CSP se define con variables X, dominio D (valores posibles) y restricciones C. En el coloreado de mapas, países adyacentes no pueden compartir color, p. ej. "el color de Portugal es diferente al color de España" [06:27-07:53].

Las N-reinas [26:55-29:47]

Problema clásico: colocar N reinas en un tablero N×N sin que se ataquen (misma fila, columna o diagonal). Se prefieren 8 variables Q1...Q8 (una por fila) en lugar de 64 variables binarias. Se distingue modelar el problema (variables y restricciones) de diseñar el algoritmo que lo resuelve [40:45-41:47].

Tipos de restricciones y aplicaciones reales [43:33-46:29]

Restricciones fuertes (hard, deben cumplirse) y suaves (preferencias que representan costos); el curso se enfoca en las fuertes. Variables discretas y continuas (programación lineal); aquí se trabajan discretas. Aplicaciones: calendarios de vuelos y tripulaciones de aerolíneas, distribución y transporte, calendarios deportivos (NBA), planificación de fábricas, asignación de aeronaves y la compensación multilateral de deudas entre bancos en México (un grafo con pesos y muchos nodos).

Backtracking [46:45-49:35]

Componentes de un CSP: estado inicial, función de transición/sucesor, prueba de meta (solución completa) y restricciones. El algoritmo asigna una variable a la vez (las variables son conmutativas) en un orden fijo, revisa restricciones en cada paso y solo prueba valores sin conflicto con asignaciones previas; es una búsqueda en profundidad con poda y, si no hay asignación posible, regresa (backtrack). Con él se resuelve N-reinas hasta N≈25: "nunca vamos a hacer todas las permutaciones". Mejoras: orden de asignación de variables y orden de valores.

Forward checking y MAC [60:28-69:58]

Forward checking (revisión hacia adelante): al asignar una variable se eliminan de los dominios de los vecinos los valores incompatibles (propagación de restricciones / consistencia de arcos). Si una variable queda con un único valor, se propaga a sus vecinos. Si un dominio se vacía, esa rama falla. MAC combina la búsqueda en profundidad con un ciclo de consistencia de arcos [67:24-69:58].

Heurísticas de ordenamiento y pseudocódigo [80:00-82:02]

MRV (valor mínimo restante): elegir la variable más restringida, con menos valores disponibles. LCV (valor menos limitante): elegir el valor que menos restricciones imponga a las demás. El backtracking recursivo: si todas las variables están asignadas, devolver la asignación; si no, seleccionar una variable no asignada y probar cada valor consistente, desasignando si la rama falla. En el cierre se mencionaron librerías y software de CSP [82:06-82:35], pero el tramo es muy ruidoso [parte no entendida].

Metaheurísticas: búsqueda local y hill climbing [Conferencia IA 6]

La búsqueda local parte de asignaciones completas y las mueve con movimientos locales: es más rápida y eficiente en memoria, pero incompleta y subóptima. En problemas de satisfacción se parte de una configuración no factible hacia una factible; en optimización, de soluciones subóptimas hacia la óptima. Hill climbing: iniciar en cualquier estado y moverse siempre al mejor vecino; si no hay mejor vecino, terminar.

Búsqueda tabú [Conferencia IA 6]

Es un hill climber con memoria: mantiene una lista tabú τ de asignaciones ya visitadas. Algoritmo: 1) dada una asignación s, generar una n que no esté en la lista; 2) elegir el mejor vecino n que no esté en la lista y hacer s←n; 3) añadir n a τ. Se regresa la mejor solución vista.

Recocido simulado [Conferencia IA 6]

Escapa de óptimos locales aceptando a veces movimientos peores. Algoritmo: 1) iniciar en un estado s con temperatura t alta; 2) seleccionar una asignación n del vecindario; 3) si f(n) > f(s), aceptar s←n; 4) si no, aceptar s←n con probabilidad e^((f(n)−f(s))/t); 5) actualizar la temperatura t ← α·t. Temperatura alta → búsqueda casi aleatoria; temperatura baja → se comporta como hill climber. Con tiempo infinito puede demostrarse su optimalidad.

t_k+1 = α · t_k  ·  P(aceptar peor) = e^{((f(n)−f(s))/t)} [Conferencia IA 6]

Algoritmos evolutivos [Conferencia IA 6]

Inspirados en la evolución natural y la supervivencia del más apto. Elementos: codificar las estructuras a replicar, operaciones (cruza y mutación), función de aptitud y mecanismo de selección. Tipos: estrategias evolutivas, programación evolutiva y algoritmos genéticos. Algoritmo básico: población inicial aleatoria, calcular aptitud, seleccionar probabilísticamente por aptitud (p. ej. selección por torneo), aplicar cruza y mutación, y ciclar hasta la condición. En la representación binaria la cadena completa es el cromosoma, cada subcadena por variable es un gen y cada valor es un alelo. La cruza de un punto corta a los padres en una posición aleatoria e intercambia las colas (existen cruzas de 2, 3... n puntos). La mutación cambia cada alelo con probabilidad P_m, normalmente muy baja.

P_m = 1 / L  (L = tamaño del cromosoma) [Conferencia IA 6]

Notas generales y no free lunch [Conferencia IA 6]

Problemas discretos/combinatorios → preferir búsqueda tabú y recocido simulado; problemas continuos o mixtos → algoritmos evolutivos suelen dar buenos resultados. Los evolutivos también se usan para generar software (programación genética), aprendizaje automático evolutivo y redes neuronales (neuroevolución). El teorema del no free lunch afirma que ningún algoritmo supera a todos los demás en todos los problemas. El siguiente tema será búsqueda con adversarios.

Complementos y precisiones (búsqueda local)

• Nota sobre el material: la búsqueda tabú, la selección por torneo y la fórmula P_m = 1/L provienen de la metaheurística clásica y de la conferencia; no aparecen en Russell y Norvig (AIMA).
• Random-restart hill climbing: repetir hill climbing desde muchos inicios aleatorios; es completo con probabilidad 1 (en 8-reinas encuentra solución en ~7 reinicios, p ≈ 0.14 por intento).
• Haz local (local beam search): mantiene k estados; en cada paso genera todos los sucesores de los k y conserva los k mejores. Los hilos comparten información (no son reinicios independientes); puede perder diversidad si los k se agrupan.
• Haz estocástico (stochastic beam search): elige los sucesores con probabilidad proporcional a su valor (aumenta la diversidad).
• Elitismo y culling: conservar los mejores padres de la generación anterior (elitismo) o descartar a los individuos por debajo de un umbral (culling).
• Espacios continuos: se usa el gradiente (subida/bajada de gradiente) para elegir la dirección de mejora.
• Recocido simulado: converge al óptimo si la temperatura baja suficientemente despacio (esquema logarítmico); en la práctica basta un enfriamiento geométrico t_k+1 = α·t_k.

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

No se indicaron en esta clase tareas con fecha de entrega.

El inicio de la clase incluyó comentarios sobre la Tarea 1 [00:00-04:00], aunque el tramo es muy ruidoso [parte no entendida].

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

6 Glosario de términos

• CSP: problema definido por variables, dominios y restricciones cuya solución es una asignación completa que las cumple.
• Backtracking: búsqueda en profundidad con poda que asigna una variable a la vez y regresa cuando no hay asignación válida.
• Forward checking: técnica que al asignar una variable elimina de los dominios de los vecinos los valores incompatibles.
• MAC: mantener consistencia de arcos durante la búsqueda en profundidad.
• MRV: heurística que elige la variable con menos valores disponibles.
• LCV: heurística que elige el valor que menos restricciones impone a las demás variables.
• Hill climbing: búsqueda local que siempre se mueve al mejor vecino y se detiene si no hay mejora.
• Búsqueda tabú: hill climber con lista de estados ya visitados para evitar ciclos.
• Recocido simulado: metaheurística que acepta movimientos peores con cierta probabilidad según una temperatura que se enfría.
• Algoritmo evolutivo: método inspirado en la evolución natural que usa población, aptitud, selección, cruza y mutación.
• Cromosoma / gen / alelo: en representación binaria, la cadena completa, cada subcadena por variable y cada valor, respectivamente.
• No free lunch theorem: teorema que afirma que ningún algoritmo de búsqueda supera a todos los demás en todos los problemas.
• Random-restart hill climbing: repetir hill climbing desde muchos inicios aleatorios; completo con probabilidad 1.
• Haz local (local beam search): mantiene k estados y sus mejores sucesores, compartiendo información entre hilos.
• Haz estocástico (stochastic beam search): como el haz local pero eligiendo por probabilidad proporcional al valor.
• Elitismo: conservar los mejores individuos de la generación anterior para que la aptitud no empeore.

7 Mapa mental textual

• Inteligencia Artificial · Clase 6
  • Problemas de satisfacción de restricciones (CSP)
    • Variables, dominios, restricciones
    • Ejemplos: Sudoku, coloreado de mapas, N-reinas
    • Restricciones fuertes vs suaves; variables discretas vs continuas
    • Aplicaciones: aerolíneas, transporte, deportes, fábricas, banca
    • Algoritmos de solución
      • Backtracking (búsqueda en profundidad con poda)
      • Forward checking (propagación de dominios)
      • MAC (consistencia de arcos + búsqueda en profundidad)
      • Heurísticas MRV y LCV
  • Metaheurísticas (búsqueda local)
    • Hill climbing
    • Búsqueda tabú (lista τ de visitados)
    • Recocido simulado (temperatura y probabilidad)
    • Algoritmos evolutivos
      • Población, aptitud, selección por torneo
      • Cruza y mutación (cromosoma, gen, alelo)
      • Tipos: estrategias evolutivas, programación evolutiva, algoritmos genéticos
    • Elección según el problema (discreto/continuo)
    • No free lunch theorem
  • Siguiente tema: búsqueda con adversarios